/*
 * @lc app=leetcode.cn id=365 lang=javascript
 *
 * [365] 水壶问题
 */

// @lc code=start
/**
 * @param {number} jug1Capacity
 * @param {number} jug2Capacity
 * @param {number} targetCapacity
 * @return {boolean}
 */

// x: 当前杯中水量， X: 杯子容量
function getNext(k, x, X, y, Y){
  switch(k){
    case 0:  // x倒空
      return [0, y];
    case 1: 
      return [x, 0];
    case 2: // x倒满
      return [X, y];
    case 3: 
      return [x, Y];
    case 4: // x倒入y中；x->y
      var diff = Math.min(x, Y-y);
      return [x - diff, y + diff];
    case 5: // y->x
      var diff = Math.min(X-x, y);
      return [x + diff, y - diff];
  }
};

/**
 * 广搜算法
 * 放入第一个状态
 * 队首弹出状态，扩展其他可能的状态。
 */
var canMeasureWater = function(jug1Capacity, jug2Capacity, targetCapacity) {
  const q = [];
  const vis = {}; // 记录发生过的状态，放置重复循环

  q.push([0, 0]);
  vis["00"] = true;

  while(q.length){
    const cur = q.pop();
    if(cur[0] + cur[1] === targetCapacity ) return true;

    for (let i = 0; i < 6; i++) {
      const nextStatu = getNext(i, cur[0], jug1Capacity,  cur[1], jug2Capacity, targetCapacity);
      const key = nextStatu[0] + "" + nextStatu[1];
      if(vis[key]) continue;
      q.push(nextStatu);
      vis[key] = true;
    }
  }
  return false;
};
// @lc code=end

